package com.reform.utils;


public class JaroWinklerDistance {

    private static float p = 0.1f;
    private static float MAX_P = 0.25f;
    private static int MAX_L = 4;

    public static float getJaroDistance(CharSequence s1, CharSequence s2) {
        if (s1 == null || s2 == null)
            return 0f;
        int result[] = matches(s1, s2);
        float m = result[0];
        if (m == 0f)
            return 0f;

        float j = ((m / s1.length() + m / s2.length() + (m - result[1]) / m)) / 3;
        return j;
    }

    public static float getJaroWinklerDistance(CharSequence s1, CharSequence s2) {
        if (s1 == null || s2 == null)
            return 0f;
        int result[] = matches(s1, s2);

        float m = result[0];
        if (m == 0f)
            return 0f;

        float j = ((m / s1.length() + m / s2.length() + (m - result[1]) / m)) / 3;
        float jw = j + Math.min(p, MAX_P) * result[2] * (1 - j);
        return jw;

    }

    private static int[] matches(CharSequence s1, CharSequence s2) {
        // 用max来保存较长的字符串，min保存较短的字符串
        // 这是为了以短字符串为行元素遍历，长字符串为列元素遍历。
        CharSequence max, min;
        if (s1.length() > s2.length()) {
            max = s1;
            min = s2;
        } else {
            max = s2;
            min = s1;
        }

        // 匹配窗口的大小，对于每一行i，列j只在(i-matchedwindow,i+matchedwindow)内移动，
        // 在该范围内遇到相等的字符，表示匹配成功
        int matchedWindow = Math.max(max.length() / 2 - 1, 0);
        // 记录字符串的匹配状态，true表示已经匹配成功
        boolean[] minMatchFlag = new boolean[min.length()];
        boolean[] maxMatchFlag = new boolean[max.length()];
        int matches = 0;

        for (int i = 0; i < min.length(); i++) {
            char minChar = min.charAt(i);
            // 列元素的搜索：j的变化包括i往前搜索窗口长度和i往后搜索窗口长度。
            for (int j = Math.max(i - matchedWindow, 0); j < Math.min(i + matchedWindow + 1, max.length()); j++) {
                if (!maxMatchFlag[j] && minChar == max.charAt(j)) {
                    maxMatchFlag[j] = true;
                    minMatchFlag[i] = true;
                    matches++;
                    break;
                }
            }
        }
        // 求转换次数和相同前缀长度
        int transpositions = 0;
        int prefix = 0;

        int j = 0;
        for (int i = 0; i < min.length(); i++) {
            if (minMatchFlag[i]) {
                while (!maxMatchFlag[j])
                    j++;

                if (min.charAt(i) != max.charAt(j)) {
                    transpositions++;
                }
                j++;
            }
        }

        for (int i = 0; i < min.length(); i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                prefix++;
            } else {
                break;
            }
        }

        return new int[] { matches, transpositions / 2, Math.min(prefix, MAX_L)};
    }

    public static float levenshtein(String str1,String str2) {
        //计算两个字符串的长度。
        int len1 = str1.length();
        int len2 = str2.length();
        //建立上面说的数组，比字符长度大一个空间
        int[][] dif = new int[len1 + 1][len2 + 1];
        //赋初值，步骤B。
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        //计算两个字符是否一样，计算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                //取三个值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
                        dif[i - 1][j] + 1);
            }
        }
        return 1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
    }

    //得到最小值
    private static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
    }
}
